# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 10_bucket_sort.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/21 13:36
------------------------------------------
    桶排序
"""


def bucket_sort(array):
    # 1.计算出数列的最大值和最小值，并计算出差值d
    max_value = array[0]
    min_value = array[0]

    for array_cell in array:
        if array_cell > max_value:
            max_value = array_cell

        if array_cell < min_value:
            min_value = array_cell

    d = max_value - min_value

    # 2. 初始化桶
    bucket_num = len(array)
    bucket_list = []
    for _ in range(bucket_num):
        bucket_list.append([])

    # 3.遍历原始数组，将每个元素放入桶中
    # (bucket_num - 1) / d 可以理解为单位长度上的桶索引长度
    for i in range(len(array)):
        num = int((array[i] - min_value) * (bucket_num - 1) / d)
        bucket = bucket_list[num]
        bucket.append(array[i])

    # 4.对每个桶内部进行排序
    for i in range(len(bucket_list)):
        # list 采用了归并排序或归并的优化版本
        bucket_list[i].sort()

    # 5.输出全部元素
    sorted_array = []
    for sub_list in bucket_list:
        sorted_array.extend(sub_list)

    return sorted_array


def demo():
    my_array = [4.12, 6.421, 0.0023, 3.0, 8.122, 4.12, 10.09]
    print(f"排序前：{my_array}")
    print(f"排序后：{bucket_sort(my_array)}")


if __name__ == '__main__':
    demo()
